package buaa.leetcode.DynamicPrograming;

public class EditDistance {
	public static int minDistance(String word1, String word2) {
		int word1Len = word1.length();
		int word2Len = word2.length();
        if(word1Len == 0 || word2Len == 0){
        	return (word1Len == 0) ? word2Len : word1Len;
        }
        int[][] table = new int[word1Len + 1][word2Len + 1];
        for(int i = 0 ;i <= word1Len ; i++){
        	table[i][0] = i;
        }
        for(int j = 0 ;j <= word2Len ; j++){
        	table[0][j] = j;
        }
		return dp(table, word1, word2, word1Len, word2Len);
    }
	private static int dp( int[][] table,String word1, String word2, int word1Len, int word2Len){
		if(word1Len == 0 || word2Len == 0){
            return word1Len > word2Len ? word1Len : word2Len;
		}
		if(table[word1Len][word2Len] > 0){
			return table[word1Len][word2Len];
		}
		char c1 = word1.charAt(word1Len - 1);
		char c2 = word2.charAt(word2Len - 1);
		if(c1 == c2){
			return dp(table, word1, word2, word1Len - 1, word2Len - 1);
		}else{
			int insert = dp(table, word1, word2, word1Len, word2Len - 1) + 1;
			int delete = dp(table, word1, word2, word1Len - 1, word2Len) + 1;
			int replace = dp(table, word1, word2, word1Len - 1, word2Len - 1) + 1;
			int min = Math.min(insert, Math.min(delete, replace));
			table[word1Len][word2Len] = min;
			return min;
		}
	}
	
	public static void main(String[] args) {
		System.out.println(minDistance("sea", "eat"));

	}

}
